package com.linkedList;

public class LinkedList<E> {
    private class Node<E>{
        public E node;
        public Node next;


        public Node(E node, Node next) {
            this.node = node;
            this.next = next;
        }
        public Node(E node){
            this.node = node;
            this.next = null;
        }


        @Override
        public String toString() {
            return "Node{" + "node=" + node + ", next=" + next + '}';
        }
    }
    private Node<E> dummyHead;
    private int size;

    public LinkedList() {
        this.dummyHead = new Node<>(null, null);
        this.size = 0;
    }

    public int getSize(){
        return size;
    }
    public boolean isEmpty(){
        return size == 0;
    }

    //向指定索引位置插入元素
    //练习用，链表一般不需要这种操作
    public void add(E e, int index){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("add failed. illegal index");
        }

        Node<E> pre = dummyHead;
        //找到插入位置前一个位置
        for(int i = 0; i < index; i++){
            pre = pre.next;
        }
        //1.新建节点 2.新建节点下一节点指向这个位置原来的节点 3.这个位置前一节点指向新建节点
//            Node<E> node = new Node<>(e);
//            node.next = pre.next;
//            pre.next = node;

        pre.next = new Node(e, pre.next);
        size++;

    }

    public void addLast(E e){
        add(e, size);
    }
    public void addFirst(E e){
        add(e, 0);
    }
    //练习，获取元素
    public E get(int index){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("get failed, illegal index");
        }
        Node<E> current = dummyHead;
        for(int i = 0; i < index; i++){
            current = current.next;
        }
        return current.node;
    }

    public E remove(int index){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("get failed, illegal index");
        }
        Node<E> pre = dummyHead;

        for(int i = 0; i < index; i++){
            pre = pre.next;
        }
        E removed = (E)pre.next.node;
        if(index == size - 1){
            pre.next = null;
        }else{
            pre.next = pre.next.next;
        }
        size--;
        return removed;
    }

    public E removeFirst(){
        return remove(0);
    }
    public E getFirst(){
        return get(1);
    }
    public boolean contines(E e){
        Node<E> current = dummyHead.next;
        while (current != null){
            if(current.node.equals(e)){
                return true;
            }
            current = current.next;
        }
        return false;
    }

    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        Node<E> cur = dummyHead.next;
        while (cur != null){
            sb.append(cur.node);
            sb.append("->");
            cur = cur.next;
        }
        sb.append("NULL");
        return sb.toString();
    }
}
